/**
 * Created by sunchenglin on 2017/7/17.
 *桶排序
 //    基数排序
 //    拓扑排序
 //    外部排序
 */
public class Solution {
    public static void change(int i, int j, int[] array){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static int getmax(int[] array){
        int max=0;
        for(int i=0;i<array.length;i++){
            if(array[i]>max){
                max = array[i];
            }
        }
        return max;
    }
//数组A 0,n存放输入数组
//数组C 0，K 存放数的个数
//根据C覆盖数组array

    public static void countingSort(int[] array){
        int[] c = new int[getmax(array)+1];
        for(int i=0; i<c.length; i++){
            c[i] = 0;
        }
        for(int i=0; i<array.length; i++){
            c[array[i]]++;
        }
        for(int k=0, i=0;i<c.length;i++){
            for(int j=c[i]; j>0;j--){
                array[k++] = i;
            }
        }
        System.out.println("hah");
    }

    public static void main(String args[]){
        int[] a={7,4,8,5,3,4,5,2,6};
        countingSort(a);
        System.out.println("haha");
    }
}
